package com.lun.swordtowardoffer2.c15;

import java.util.LinkedList;
import java.util.Queue;

public class FindCircleNum {
	
	//应用图搜索解决问题
	public int findCircleNum(int[][] M) {
		boolean[] visited = new boolean[M.length];
		int result = 0;
		for(int i = 0; i < M.length; i++) {
			if(!visited[i]) {
				findCircle(M, visited, i);
				result++;
			}
		}
		
		return result;
	}

	private void findCircle(int[][] M, boolean[] visited, int i) {
		Queue<Integer> queue = new LinkedList<>();
		
		queue.offer(i);
		visited[i] = true;
		
		while(!queue.isEmpty()) {
			int t = queue.poll();
			for(int friend = 0; friend < M.length; friend++) {
				if(!visited[friend] && M[t][friend] == 1) {
					queue.offer(friend);
					visited[friend] = true;
				}
			}
		}
	}
	
	//应用并查集解决问题
	public int findCircleNum2(int[][] M) {
		int[] fathers = new int[M.length];
		
		for(int i = 0;i < fathers.length; i++) {
			fathers[i] = i;
		}
		
		int count = M.length;
		
		for(int i = 0; i < M.length; i++) {
			for(int j = i + 1; j < M.length; j++) {
				if(M[i][j] == 1 && union(fathers, i, j)) {
					count--;
				}
			}
		}
	
		return count;
	}
	
	public boolean union(int[] fathers, int i, int j) {
		int fatherOfI = findFather(fathers, i);
		int fatherOfJ = findFather(fathers, j);
		
		if(fatherOfI != fatherOfJ) {
			fathers[fatherOfI] = fatherOfJ;
			return true;
		}
		return false;
	}
	
	private int findFather(int[] fathers, int i) {
		if(fathers[i] != i) {
			fathers[i] = findFather(fathers, fathers[i]);
		}
		return fathers[i];
	}
}
